import java.util.*;

//单词接龙
//测试链接： https://leetcode.cn/problems/word-ladder/
public class LadderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>();
        Set<String> vis = new HashSet<>();
        for (String s : wordList)
            words.add(s);

        int len = endWord.length();
        int ans = 0;
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);

        while (!q.isEmpty()) {
            ans++;
            int size = q.size();
            while (size-- != 0) {
                String str = q.poll();

                for (int j = 0; j < len; j++) {
                    for (int i = 0; i < 26; i++) {
                        char[] temp = str.toCharArray();

                        temp[j] = (char)('a'+i);
                        String s = new String(temp);
                        if (words.contains(s) && !vis.contains(s)) {
                            if (s.equals(endWord)) return ans+1;

                            System.out.println(s);
                            q.add(s);
                            vis.add(s);
                        }
                    }

                }

            }
        }
        return 0;
    }
}
